Nowadays, a flash memory is widely used in a computer motherboard or a consumptive electronic product, such as the flash memory of a thumb disk or a MP3 player. The conventional NAND (Not AND) type of flash memory is utilized in an embedded storage system. The flash memory is composed of a plurality of pages and the storage volume, e.g. 512 kilo-bytes (KB), of each page is invariant, wherein a block is composed of some continuous pages, e.g. 32 pages. However, one feature of the flash memory is that the same page in a block cannot be written unless the block corresponding to the same page is erased before performing writing procedure on the flash memory. Therefore, because of the feature mentioned above, it is difficult to control the flash memory for memory management.
The conventional method is employed in an address translation table by a maintenance manner so that the flash memory can be operated in an original file system, such as an original file system or file format, e.g. file allocation table (FAT16), FAT32, new technology file system (NTFS) or second extended file system (EXT2), etc. The method is that the logic addresses are mapped to the physical addresses of the flash memory, respectively, for simulating the flash memory as the memory having continuous addresses. Therefore, the flash memory can be regarded as a hard disk without modifying any original set. Accordingly, the method is called NTFL (NAND flash translation layer) manner.
Please refer to FIG. 1. FIG. 1 illustrates an architecture diagram of a conventional flash translation layer used in the flash memory. As shown in FIG. 1, the flash memory “X” is composed of a plurality of blocks. In addition, an addressing basic unit and a converting basic unit of the flash translation layer is based on block-level. The block-level includes two different addressing blocks, a primary block “X1” and a replacement block “X2” corresponding to the primary block “X1”. The primary block “X1” has eight pages from page “X10” to page “X17”; likewise the replacement block “X2” also has eight pages from page “X20” to page “X27”. In addition, the replacement block “X2” is used to store the data which are unable to be written into the primary block “X1”.
When the amount “n” of logic block address (LBA) is written into the flash memory, the flash translation layer calculates two values, including a virtual block address (VBA) value and a block offset (BO) value. The virtual block address (VBA) value can be represented by the following formula: n/b, wherein “n” is the amount of logic block addresses (LBA) and “b” is the amount of the pages in a block. The block offset (BO) value can be represented by the following formula: n % b, which is the remainder by dividing “n” by “b”. Due to the virtual block address (VBA), the conventional flash translation layer finds out the addresses of the primary block “X1” and the replacement block “X2” corresponding to a writing procedure.
The conventional flash translation layer writes the data into the page of the primary block “X1” according to the block offset value. However, if the page is written therein previously, the conventional flash translation layer writes the data into a free page of the replacement block “X2”. In addition, it assumes that the data are written into the first page “X20” to the last page “X27” of the replacement block “X2”. Further, if the page “X20” to page “X27” of the replacement block “X2” are written completely, the conventional flash translation layer writes the un-overdue data in the primary block “X1” and the replacement block “X2” to a new primary block “X1”. In addition, the conventional flash translation layer updates a coarse-grained table (CGT), as shown in FIG. 2, so that the coarse-grained table is mapped to the new primary block “X1”.
In an example of FIG. 1, the logic block address (LBA) value “1011” is written to explain the procedure of the conventional flash translation layer. Accordingly, the virtual block address is “126” which is obtained by dividing 1011 by 8, i.e. the following formula: 1101/8=126. The block offset (BO) value is “3”, which is obtained by subtracting 8 multiply 126 from 1011, i.e. the following formula: 1101−8*126=3. As shown in FIG. 1, the content of the virtual block address value “126” is represented by the indication (9, 23). That is, the writing address in the primary block “X1” is “9” and the writing address in the replacement block “X2” is “23”. Furthermore, the data is written into the page “X13” of the primary block “X1” according to the block offset value “3”. However, if the page “X13” is written previously, i.e. not available, the data are written into the first free page of the replacement block “X2”, as shown in the page X22 in FIG. 1. Therefore, the conventional flash translation layer completes the writing procedure of the data corresponding to the logic block address value “1011”.
Please refer to FIG. 2. FIG. 2 illustrates a null data collection procedure of a conventional flash translation layer used in a flash memory. It assumes that there are five different logic block addresses, i.e. “A”, B”, “C”, “D”, and “E”, and the data allocation corresponding to the logical block addresses is shown in FIG. 2. When the replacement block “X2” are written completely, it is required to perform the null data collection procedure. Accordingly, the null data collection procedure duplicates all the pages in the primary block address value, “PPBA=1” and the replacement block address value, “PPBA=2” of the primary block “X1” to a new primary block address value, “PPBA=3”, and then the primary block address value, “PPBA=1” and the replacement block address value, “PPBA=2” are erased. In addition, a writing procedure performed by the coarse-grained table (CGT) records the primary block address value, “PPBA=3” and the replacement block address “RPBA” is set as empty, the value of the replacement block address “RPBA” is “−1”. The operations of the null data collection procedure are illustrates by the arrow indications, as shown in FIG. 2. However, the drawback of the conventional flash translation layer is to restrict the amount of the replacement block “X2”. If the amount of the replacement block “X2” exceeds the limit, it is required to perform the null data collection procedure for reducing the amount of the replacement block “X2”. Therefore, the conventional flash translation layer repeatedly performs the null data collection procedure and occupies more and more memory.
When the volume of the flash memory is increasingly enlarged, the conventional flash translation layer needs to maintain the address translation table and employ the block-level manner for economizing the spaces of the random access memory. However, while performing the block-level manner, it is inefficient that the logic addresses are mapped to the physical addresses of the flash memory. Since the reading and writing the data procedure regards the page as the accessing unit, thus it takes a long time to search a page of one block in order to obtain the latest physical address of the page during the block-level procedure. Therefore, the efficiency of the reading and writing procedure of the data and operation speed of the flash memory are decreased disadvantageously.
In addition, a related art in TW Patent No. I253564, entitled Method of Efficient Data Management with Flash Storage System is disclosed, and more particularly to an addressing procedure for the reading and writing procedure of the data and the method for managing the good blocks and the bad blocks for the conventional flash memory. Furthermore, another related art in TW Patent No. 1249670, entitled System and Method Capable of Sequentially Writing A Flash Memoryis disclosed, and more particularly to the virtual block which is capable of sequentially writing the data into the flash memory. However, it is inefficient that the logic addresses are mapped to the physical addresses of the flash memory in the above-mentioned prior arts. Further, the operation speed of the flash memory is decreased disadvantageously.